package com.leetcode.根据数据结构分类.数组;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2020/12/16
 * @description: 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
 * https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
 */
public class A_剑指_Offer_21_调整数组顺序使奇数位于偶数前面 {

	/**
	 * 创建一个定长的数组，然后遍历一遍；
	 * 通过双指针将元素放到对应的位置
	 *
	 * @param nums
	 * @return
	 */
	public int[] exchange(int[] nums) {
		int[] res = new int[nums.length];
		int headIndex = 0;
		int tailIndex = nums.length - 1;
		for (int i = 0; i < nums.length; i++) {
			if (isOddNum(nums[i])) {
				res[headIndex++] = nums[i];
			} else {
				res[tailIndex--] = nums[i];
			}
		}
		return res;
	}

	/**
	 * 自从学会了 hash 以后，就知道了使用 位运算& 来取代 取模运算！
	 *
	 * @return
	 */
	public boolean isOddNum(int num) {
		return (num & 1) == 1;
	}

	int tempNum = 0;

	/**
	 * 上面我自己的方案中需要创建一个新的数组，性能较差！
	 * 参考了题解：
	 * 1.从左边找到 偶数；从右边找到奇数；
	 * 2.进行交换；直到指针碰撞
	 *
	 * @param nums
	 * @return
	 */
	public int[] exchange2(int[] nums) {
		int left = 0;
		int right = nums.length - 1;
		boolean leftFind = false;
		boolean rightFind = false;
		while (left < right) {
			//找到 left == even number
			while (!leftFind && left < right) {
				if (!isOddNum(nums[left])) {
					leftFind = true;
					break;
				}
				left++;
			}
			while (!rightFind && left < right) {
				if (isOddNum(nums[right])) {
					rightFind = true;
					break;
				}
				right--;
			}
			//找到 right == odd number

			//swap
			swap(nums, left++, right--);
			leftFind=false;
			rightFind=false;
		}
		return nums;
	}


	/**
	 * 交换 nums 中 index1 和 index2 的元素
	 *
	 * @param nums
	 * @param index1
	 * @param index2
	 */
	public void swap(int[] nums, int index1, int index2) {
		tempNum = nums[index1];
		nums[index1] = nums[index2];
		nums[index2] = tempNum;
	}


	public static void main(String[] args) {
		int[] nums = new int[]{1,3,5};
		A_剑指_Offer_21_调整数组顺序使奇数位于偶数前面 action = new A_剑指_Offer_21_调整数组顺序使奇数位于偶数前面();
		int[] ints = action.exchange2(nums);
		System.out.println(Arrays.toString(ints));
	}
}
